package test;


import java.util.HashMap;
/**
 * LRU缓存算法
 * @author 豆包LU
 * @date 2023/4/10 17:08
 */
public class LRUCache {
    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);

        cache.put(1, 1);
        Node put = cache.put(2, 2);
        System.out.println("头结点后的节点即第一个节点value为:"+put.value+"--第二个节点value为："+put.next.value);
        Node x = cache.get(1);
        // 输出1
        System.out.println(x.value);
        System.out.println("头结点后的节点即第一个节点value为:"+x.value+"--第二个节点value为："+x.next.value);
        Node put1 = cache.put(3, 3);
        System.out.println("头结点后的节点即第一个节点value为:"+put1.value+"--第二个节点value为："+put1.next.value);
        // 输出null,表示节点2不存在，因最近未使用已被清除
        System.out.println(cache.get(2));
        Node put2 = cache.put(4, 4);
        System.out.println("头结点后的节点即第一个节点value为:"+put2.value+"--第二个节点value为："+put2.next.value);

        // 输出null,表示节点1不存在，因最近未使用已被清除
        System.out.println(cache.get(1));
        // 输出3
        System.out.println(cache.get(3).value);
        // 输出4
        System.out.println(cache.get(4).value);

    }

    /**
     * Desc:定义一个节点类
     * @author 豆包LU
     * @date 2023/4/10 17:08
     */
    class Node {
        int key;
        int value;
        Node prev;
        Node next;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    // 定义LRU缓存的容量大小
    private int capacity;

    // 使用HashMap存储key和对应节点的映射关系，实现O(1)的查找
    private HashMap<Integer, Node> map = new HashMap<>();

    // 定义双向链表的头尾节点
    private Node head;
    private Node tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;

        // 初始化双向链表的头尾节点
        head = new Node(0, 0);
        tail = new Node(0, 0);

        // 头尾节点互相指向，表示空链表
        head.next = tail;
        tail.prev = head;
    }

    public Node get(int key) {
        if (map.containsKey(key)) {
            // 如果key已经存在于缓存中，则将其移到链表头部，表示最近被访问
            Node node = map.get(key);
            removeNode(node);
            addNodeToHead(node);
            return node;
        } else {
            // 如果key不存在于缓存中，则返回-1
            return null;
        }
    }

    public Node put(int key, int value) {
        if (map.containsKey(key)) {
            // 如果key已经存在于缓存中，则更新节点的值，并将其移到链表头部，表示最近被访问
            Node node = map.get(key);
            node.value = value;
            removeNode(node);
            Node node1 = addNodeToHead(node);
            return node1;
        } else {
            // 如果key不存在于缓存中，则创建一个新节点，并将其加入链表头部，表示最近被访问
            Node node = new Node(key, value);
            map.put(key, node);
            Node node1 = addNodeToHead(node);

            // 如果缓存已满，则删除链表尾部的节点，表示最近最少使用
            if (map.size() > capacity) {
                Node tailNode = tail.prev;
                map.remove(tailNode.key);
                removeNode(tailNode);
            }
            return node1;
        }
    }

    // 将节点从链表中删除
    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    // 将节点加入链表头部
    private Node addNodeToHead(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
        Node headNext = head.next;
        return headNext;
    }
}

